/**
 *  @file FindCommonNode.c
 *  @desc 给定两个不带有头节点的单链表，找出它们的第一个公共结点
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-03 10:55
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct node {
    int data;             // 数据域
    struct node *next;    // 指向下一个节点
} node, *link;             // link 是指向 node 结构体的指针类型

// 创建一个新节点
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 尾部插入
void insertTail(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

void printList(link head) {
    if (head == NULL) return;
    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int getLength(link head) {
    int length = 0;
    if (head == NULL) return length;
    link cur = head;
    while (cur != NULL) {
        length ++;
        cur = cur->next;
    }
    return length;
}

link findCommonNode(link l1, link l2) {
    if (l1 == NULL) return NULL;
    if (l2 == NULL) return NULL;
    int l1_length = getLength(l1);
    int l2_length = getLength(l2);
    int dif = l1_length - l2_length;
    if (dif > 0 ) {
        while (dif --) l1 = l1->next;
    }else {
        dif = -dif;
        while (dif --) l2 = l2->next;
    }

    while (l1 != NULL && l2 != NULL) {
        if (l1 == l2) {
            return l1;
        }
        l1 = l1->next;
        l2 = l2->next;
    }

}


int main() {
    // 初始化两个带头节点的链表
    link head1 = NULL, head2 = NULL;

    // 创建公共部分链表：6 → 7
    link common = createNode(6);
    common->next = createNode(7);

    // 构造链表1：1 → 2 → 3 → 6 → 7
    insertTail(&head1, 8);
    insertTail(&head1, 2);
    insertTail(&head1, 1);
    link p = head1;
    while (p->next != NULL) p = p->next;
    p->next = common;  // 链接公共部分

    // 构造链表2：4 → 5 → 6 → 7（与链表1共用尾部）
    link node5 = createNode(5);
    node5->next = common;
    link node4 = createNode(4);
    node4->next = node5;
    insertTail(&head2, 8);
    head2->next = node4;

    // 打印两个链表
    printf("List 1:\n");
    printList(head1);
    printf("List 2:\n");
    printList(head2);


    // 查找第一个公共节点
    link commonNode = findCommonNode(head1, head2);
    if (commonNode) {
        printf("First common node value: %d\n", commonNode->data);
    } else {
        printf("No common node found.\n");
    }

    return 0;
}